/*
给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。

子数组 是数组的一段连续部分。

 

示例 1：

输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
示例 2：

输入：nums = [0,0,0,0,0], goal = 0
输出：15
 

提示：

1 <= nums.length <= 3 * 104
nums[i] 不是 0 就是 1
0 <= goal <= nums.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-subarrays-with-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

// 哈希表
class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int res{0};
        unordered_map<int, int> hashMap{};
        int sum{0};
        for (int& num : nums) {
            ++hashMap[sum];
            sum += num;
            res += hashMap[sum - goal];
        }
        return res;
    }
};

// 滑动窗口
class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size();
        int right{0};
        int left1{0};
        int left2{0};
        int sum1{0};
        int sum2{0};
        int res{0};
        while (right < n) {
            sum1 += nums[right];
            while (left1 <= right && sum1 > goal) {
                sum1 -= nums[left1];
                ++left1;
            }
            sum2 += nums[right];
            while (left2 <= right && sum2 >= goal) {
                sum2 -= nums[left2];
                ++left2;
            }
            res += left2 - left1;
            ++right;
        }
        return res;
    }
};